package lbj.cyw.dp;
/*
* 42.接雨水
*       使用双数组 记录左右最大值
* */
public class Trap42 {
    public int trap(int[] height) {
        int n=height.length;
        int[] left=new int[n];
        int[] right=new int[n];
        int max=0;
        for(int i=0;i<n;i++){
            max=Math.max(max,height[i]);
            left[i]=max;
        }
        max=0;
        for(int i=n-1;i>=0;i--){
            max=Math.max(max,height[i]);
            right[i]=max;
        }
        int res=0;
        for(int i=0;i<n;i++){
            int min=Math.min(left[i],right[i]);
            res+=min-height[i];
        }
        return res;
    }
}
